/**
 * @file linked_list.c
 * @author 樊少冰
 * @date 2019 年 3 月 21 日
 * @desc 链表 数据结构 源文件
 * From CLC project
 */

#include "linked_list.h"
#include <base/new.h>
#include <stdlib.h>
#include <string.h>


link_t *
new_link (size_t data_size)
{
    link_t *R = (link_t*)malloc(sizeof(link_t) + data_size);
    if (R == NULL) return NULL;
    R->next = NULL;
    R->prev = NULL;
    return R;
}


linked_list_t *
new_linked_list (size_t elem_size)
{
    linked_list_t *R = NEW(linked_list_t);
    if (R == NULL) return NULL;

    R->first = NULL;
    R->last = NULL;
    R->elem_size = elem_size;
    R->length = 0;

    return R;
}


int
linked_list_append (linked_list_t *obj, void *ptr_elem)
{
    if (obj == NULL) return -1;
    if (ptr_elem == NULL) return -1;

    size_t es = obj->elem_size;

    link_t *nl = new_link(es);
    if (nl == NULL) return -1;
    memcpy((void*)nl->data, ptr_elem, es); // Copy element data

    if (obj->last != NULL) {
        obj->last->next = nl;
        nl->prev = obj->last;
        obj->last = nl;
    }
    else {
        obj->first = nl;
        obj->last = nl;
    }

    obj->length++;
    return 0;
}


link_t *
nth (linked_list_t *obj, size_t offset)
{
    if (obj == NULL) return NULL;
    if (offset >= obj->length) return NULL;

    link_t *p = NULL;

    if (offset <= obj->length / 2) {
        p = obj->first;
        for (size_t i = 0; i < offset; i++)
            p = p->next;
    }
    else {
        p = obj->last;
        for (size_t i = obj->length - 1; i > offset; i--)
            p = p->prev;
    }

    return p;
}


void *
linked_list_get (linked_list_t *obj, size_t offset)
{
    if (obj == NULL) return NULL;
    if (offset >= obj->length) return NULL;

    link_t *p = nth(obj, offset);

    if (p == NULL) return NULL;
    return (void*)p->data;
}


int
linked_list_insert (linked_list_t *obj, size_t offset, void *ptr_data)
{
    if (obj == NULL) return -1;
    if (offset > obj->length) return -1;

    link_t *p = NULL;

    if (obj->length == 0) {
        return linked_list_append(obj, ptr_data);
    }

    link_t *n = new_link(obj->elem_size);
    memcpy((void*)n->data, ptr_data, obj->elem_size);

    if (offset == 0) {
        n->next = obj->first;
        obj->first->prev = n;
        obj->first = n;
    }
    else if (offset == obj->length) {
        n->prev = obj->last;
        obj->last->next = n;
        obj->last = n;
    }
    else {
        p = nth(obj, offset);
        n->prev = p->prev;
        n->next = p;
        p->prev = n;
        n->prev->next = n;
    }

    obj->length++;
    return 0;
}


int
linked_list_delete (linked_list_t *obj, size_t offset)
{
    if (obj == NULL) return -1;
    if (offset >= obj->length) return -1;

    link_t *p;

    if (obj->length == 1) {
        if (obj->first == NULL) return -1;
        free(obj->first);
        obj->first = NULL;
        obj->last = NULL;
    }
    else if (offset == 0) {
        p = obj->first;
        if (p == NULL) return -1;
        obj->first = p->next;
        p->next->prev = NULL;
        free(p);
    }
    else if (offset == obj->length - 1) {
        p = obj->last;
        if (p == NULL) return -1;
        obj->last = p->prev;
        p->prev->next = NULL;
        free(p);
    }
    else {
        p = nth(obj, offset);
        if (p == NULL) return -1;
        p->prev->next = p->next;
        p->next->prev = p->prev;
        free(p);
    }

    obj->length--;
    return 0;
}


int
linked_list_delete_all (linked_list_t *obj)
{
    if (obj == NULL) return -1;

    link_t *p, *q;
    for (p = obj->first; p != NULL; p = q) {
        q = p->next;
        free(p);
    }

    obj->first = NULL;
    obj->last = NULL;
    obj->length = 0;

    return 0;
}


int
linked_list_concat (linked_list_t *obj, linked_list_t *another)
{
    if (obj == NULL || another == NULL)
        return -1;
    
    if (obj->elem_size != another->elem_size)
        return -2;

    if (obj->length == 0) {
        memcpy((void*)obj, (void*)another, sizeof(linked_list_t));
    }
    else if (another->length == 0) {
        // Nothing needed todo
    }
    else {
        obj->last->next = another->first;
        another->first->prev = obj->last;
        obj->last = another->last;
        obj->length += another->length;
    }

    free(another);
    return 0;
}


void
free_linked_list (linked_list_t *obj)
{
    linked_list_delete_all(obj);
    free(obj);
}
